package DataStructures.BinaryTree;

import com.mysql.jdbc.log.NullLogger;

import java.security.Principal;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author ：ALi
 * @date ：Created in 2021/12/11 14:12
 * @description：哈夫曼树
 * @modified By：
 * @version: $
 */
public class HaffmanTreeTes {
    public static void main(String[] args) {
        int[] arr = {13, 7, 8, 3, 29, 6, 1};
        Node node = HaffmanTree(arr);
        node.preShow();
    }

    public static Node HaffmanTree(int[] array) {
        List<Node> arrayList = new ArrayList<Node>();
        for (int e : array) {
            arrayList.add(new Node(e));
        }
        while (arrayList.size() > 1) {
            Collections.sort(arrayList);
            //将当前arrayList最小的两个元素添加到node中。
            Node node1 = new Node(arrayList.get(0).getValue() + arrayList.get(1).getValue());
            node1.setLeftNode(arrayList.get(0));
            node1.setRightNode(arrayList.get(1));
            //依次将最小的两个元素移除
            arrayList.remove(0);
            arrayList.remove(0);
            arrayList.add(node1);
        }
        return arrayList.get(0);


    }

}

class Node implements Comparable<Node> {
    private int value;
    private Node leftNode;
    private Node rightNode;

    public void setLeftNode(Node leftNode) {
        this.leftNode = leftNode;
    }

    public void preShow() {
        System.out.print(this.value + " ");
        if (this.leftNode != null) {
            this.leftNode.preShow();
        }
        if (this.rightNode != null) {
            this.rightNode.preShow();
        }
    }

    public void setRightNode(Node rightNode) {
        this.rightNode = rightNode;
    }

    public int getValue() {
        return value;
    }

    public Node getLeftNode() {
        return leftNode;
    }

    public Node getRightNode() {
        return rightNode;
    }

    public Node(int value) {
        this.value = value;
    }

    public Node() {
    }


    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Node node = (Node) o;

        return value == node.value;
    }

    @Override
    public int hashCode() {
        return value;
    }

    @Override
    public int compareTo(Node o) {
        //从小到大排序
        return this.value - o.value;
    }
}